package src.数据结构.映射;

public class OrderSymbolTable<Key extends Comparable<Key>, Value> {
    // 有序键值对
    private Node head;
    private int N;

    public OrderSymbolTable() {
        this.head = null;
        this.N = 0;
    }

    public Value get(Key key) {
        Node<Key, Value> n = this.head;
        if (n == null) {
            return null;
        } else {
            while (n.next != null) {
                if (n.key.equals(key)) {
                    return n.value;
                }
                n = n.next;
            }
        }
        return null;
    }

    public void put(Key key, Value value) {
        // key 存在则替换值
        Node n = this.head;
        while (n!= null) {
            if (n.key.equals(key)) {
                n.value = value;
                return;
            }
            n = n.next;
        }

        // key 不存在则创建新节点并准备插入
        Node<Key, Value> newNode = new Node<>(key, value, null);

        // 如果链表为空，直接将新节点设为头节点
        if (this.head == null) {
            this.head = newNode;
            this.N++;
            return;
        }

        // 处理新节点应插入到头节点的情况
        if (key.compareTo((Key) this.head.key) < 0) {
            newNode.next = this.head;
            this.head = newNode;
            this.N++;
            return;
        }

        // 一般情况，找到合适位置插入新节点
        Node<Key, Value> curr = this.head.next;
        Node<Key, Value> per = this.head;
        while (curr!= null && key.compareTo(curr.key) > 0) {
            per = curr;
            curr = curr.next;
        }

        // 如果当前节点的 key 与插入的 key 相同，则替换值
        if (curr!= null && key.compareTo(curr.key) == 0) {
            curr.value = value;
            return;
        }

        // 将新节点插入到合适位置
        per.next = newNode;
        newNode.next = curr;
        this.N++;
    }

    public void delete(Key key) {
        // 处理头节点的特殊情况
        if (this.head != null && this.head.key.equals(key)) {
            // 删除头节点并更新头节点
            this.head = this.head.next;
            this.N--;
            return;
        }

        Node n = this.head;
        while (n != null && n.next != null) {
            if (n.next.key.equals(key)) {
                n.next = n.next.next;
                this.N--;
                return;
            }
            n = n.next;
        }
    }

    public int size() {
        return this.N;
    }

    public void show() {
        Node n = head;
        while (n != null) {
            System.out.print(n.key + ":" + n.value + " ");
            n = n.next;
        }
        System.out.println();
    }
}
